'''
@Descripttion: 
@version: 
@encoding: utf-8
@Author: qiurongcan
Date: 2025-05-06 20:08:35
LastEditTime: 2025-09-05 20:09:43
'''
# 缺失的第一个正数

class Solution:

    def firstMissingPositive(self, nums: list[int]) -> int:
        size = len(nums)
        # 将每个正数放到它应该在的位置上
        for i in range(size):
            # 且不在对应位置上
            while 1 <= nums[i] <= size and nums[i] != nums[nums[i] - 1]:
                self.__swap(nums, i, nums[i] - 1)



        for i in range(size):
            if i + 1 != nums[i]:
                return i + 1
            
        
        return size + 1




    def __swap(self, nums, idx1, idx2):
        nums[idx1], nums[idx2] = nums[idx2], nums[idx1]



if __name__ == "__main__":

    nums = [1, 2, 0]
    sol = Solution()
    ans = sol.firstMissingPositive(nums)

    print(ans)



